package com.zjj.lbw.interview.recursion;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，
 * 随后玩家 2 继续从剩余数 组任意一端拿取分数，然后玩家 1 拿，…… 。
 * 每次一个玩家只能拿取一个分数，分数被拿取之后不再可 取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
 * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最 大化。
 * 两个值的时候必然是取较大的，三个值，取一个能使自己分数和最大的，后手必然留较小的给先手，因 此先手选一个值加上该较小值最大化 。
 * @date 2023/9/7 11:36
 */
public class CanWin {
    public static boolean canWin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int sum = Arrays.stream(nums).sum();
//        int maxScore = maxScore1(nums, l, r);
        int maxScore = maxScore2(nums, l, r);

//        return maxScore > (sum - maxScore);
        int diff = maxScore2(nums, 0, r);
        System.out.println(diff);
        return diff >= 0;
    }

    private static int maxScore1(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }
        if (r - l == 1) {
            return Math.max(nums[l], nums[r]);
        }

        // 当前选择左端点，然后
        int leftScore = nums[l] + Math.min(maxScore1(nums, l + 2, r), maxScore1(nums, l + 1, r - 1));
        int rightScore = nums[r] + Math.min(maxScore1(nums, l + 1, r - 1), maxScore1(nums, l, r - 2));

        return Math.max(leftScore, rightScore);
    }

    /**
     * 使用差值 简化递归
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private static int maxScore2(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }

        int leftScore = nums[l] - maxScore2(nums, l + 1, r);
        int rightScore = nums[r] - maxScore2(nums, l , r - 1);

        return  Math.max(leftScore, rightScore);
    }

    // 使用动态规划求解
    public static boolean canWinDp(int[] nums) {
        int length = nums.length;
        // 创建二维dp数组，dp[l][r] 含义是 l ~ r区间差值
        int[][] dp = new int[length][length];

        // 初始dp数组，按照上面差值递归的思路，是二维数组下标相等 l = r时，那差值肯定是 num[l]
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        // 从前后遍历都不影响结果
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }

//        for (int i = 0; i <= length - 2; i++) {
//            for (int j = i + 1; j < length; j++) {
//                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
//            }
//        }
        return dp[0][length - 1] >= 0;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{5, 200, 2, 3};
        int[] arr2 = new int[]{5, 200, 2, 3, 5};
        System.out.println(canWin(arr1));
        System.out.println(canWin(arr2));
        System.out.println(canWinDp(arr1));
        System.out.println(canWinDp(arr2));
    }
}
